package com.atguigu.sort;

import java.util.Arrays;

/**
 * 分治算法
 *
 * 消耗时间:
 * work: 0.011s
 * 千万: 1.03s
 * 亿级: 5.3s
 */
public class MergeSort {
    public static void main(String[] args) {
//        int[] arr={1,6,2,3,8,7,5,4,4};
        int[] arr=ArrCreator.createRandArr(ArrCreator.testVelocitySize*1000);
        int[] temp=new int[arr.length];
        ArrCreator.beforeSort();
        sort(arr,0,arr.length-1,temp);
        ArrCreator.afterSort();
//        System.out.println(Arrays.toString(arr));
    }

    /**
     * 相比快速排序, 更易理解(个人认为这一点很重要, 越容易理解的算法, 泛用性会更好)
     * 分治算法
     *
     * 分: 通过传递左索引和右索引, 作为结果递归给子数组
     * 直到二者相等, 则不再用分
     * 治: 每个分布的区分信息, 是左右索引, 而合并的左部右索引恰好与合并的右部左索引相同, 因此合并时这三部分属于核心参数
     * 而arr和temp则都属于公用部, 只是为了方便才作为参数传递
     *
     * @param arr 原始数组
     * @param leftIndex
     * @param rightIndex
     * @param temp
     */
    public static void sort(int[] arr,int leftIndex,int rightIndex,int[] temp){

        if(leftIndex<rightIndex){
            int middleIndex=(leftIndex+rightIndex)/2;
            sort(arr,leftIndex,middleIndex,temp);
            sort(arr,middleIndex+1,rightIndex,temp);
            merge(arr,leftIndex,middleIndex,rightIndex,temp);
        }
    }

    public static void merge(int[] arr,int leftBoundary,int middleBoundary,int rightBoundary,int[] temp){
        int leftIndex=leftBoundary;
        int rightIndex=middleBoundary+1;
        int tempIndex=0;
        // 合并两部的通用思路: 先考虑两部均有剩余的情况, 再单独处理仅一部有剩余的情况

        // 两部皆有剩余: 对比数组头放置temp
        while(leftIndex<=middleBoundary&&rightIndex<=rightBoundary){
            if(arr[leftIndex]<=arr[rightIndex]){
                temp[tempIndex++]=arr[leftIndex++];
            }else{
                temp[tempIndex++]=arr[rightIndex++];
            }
        }

        // 仅一部有剩余: 按序将剩余部分放置temp
        while(leftIndex<=middleBoundary){
            temp[tempIndex++]=arr[leftIndex++];
        }
        while(rightIndex<=rightBoundary){
            temp[tempIndex++]=arr[rightIndex++];
        }

        // 将temp元素拷贝至原数组中
        tempIndex=0;
        leftIndex=leftBoundary;
        while(leftIndex<=rightBoundary){
           arr[leftIndex++]=temp[tempIndex++];
        }
    }
}
